#include <iostream>
#include <numeric>
using namespace std;

#define MAX 50

int M[MAX];      // 对应每个任务的耗时
int dp[MAX]; // 该数组的意思为，容量为j的序列最多能装dp[j]耗时的任务
int n;           // n个任务

// 双核同时工作，则将任务分为两个花费时间相近的子序列，用时最短
// 也即在容量等于总任务一半的队列中，尽可能多的放入要执行的任务内容
// 递推公式：dp[j] = max(dp[j], dp[j - M[i]] + M[i])
// 即dp[j]容纳的最大耗时，要么是当前已装，要么是能容纳M[i]的最大背包装入M[i]
int min_time()
{
    int sum = std::accumulate(M, M + n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = sum / 2; j >= M[i]; j--)
            dp[j] = max(dp[j], dp[j - M[i]] + M[i]);
    }
    // (int)sum/2 小于等于 sum/2
    return (sum - dp[sum / 2]) * 1024; // 选取较大的那一半
}

int main()
{
    memset(dp, 0, sizeof(int) * MAX);
    cout << "请输入任务个数n：";
    cin >> n;
    cout << "请输入" << n << "个任务耗时：" << endl;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        M[i] = t / 1024; // 每个任务耗时1024的倍数，可以除去
    }

    cout << "最少需要处理时间：" << min_time() << endl;

    return 0;
}

/*
请输入任务个数n：5
请输入5个任务耗时：
3072 3072 7168 3072 1024
最少需要处理时间：9216
*/